package leetcode;

/**
 * 采用 前序遍历的思想去解题
 */
public class l0114_二叉树展开为链表_前序遍历_递归的方式 {

    public void flatten(TreeNode root) {
        // 递归的出口
        if (root == null) {
            return;
        }
        //1 根
        //将左子树 嫁接到 右边
        if (root.left != null) {
            //保留之前的right
            TreeNode oldRight = root.right;
            //将left 嫁接到right
            root.right = root.left;
            //清空left
            root.left = null;
            TreeNode mostRight = root;
            //将旧的right嫁接到右下角
            while (mostRight.right != null) {
                mostRight = mostRight.right;
            }
            mostRight.right = oldRight;
        }
        //2 左子树  由于不存在左子树，故不需要递归遍历
        //3 右子树
        flatten(root.right);
    }
}
